package gold.gold05;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 *
 */
public class S1624数对和 {
    /**
     * 98, 大家时间都差不多, 就这个sort比较耗时。
     */
    public List<List<Integer>> pairSums(int[] nums, int target) {
        if(nums == null || nums.length <= 1) return new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        // 因为一个数只能属于一个数对, 但是数可以重复, 所以前后两个指针。
        int pre = 0;
        int beh = nums.length - 1;
        List<List<Integer>> res = new LinkedList<>();
        loop1:
        while(beh >= 0 && pre < beh){
            while(nums[pre] + nums[beh] < target){
                pre++;
                if(!(pre < beh)) break loop1;
            }
            if(nums[pre] + nums[beh] == target){
                List<Integer> temp1 = new ArrayList<>(2);
                temp1.add(nums[pre]);
                temp1.add(nums[beh]);
                res.add(temp1);
                pre++; // 这个pre已经用过了。
            }
            beh--;
        }
        return res;
    }
    // 99, 优化一下, 改了循环的内部判断逻辑。
    // List.of()是List接口的一个静态方法, 返回一个包含传递进去元素的默认List实现。
    public List<List<Integer>> pairSums2(int[] nums, int target) {
        if(nums == null || nums.length <= 1) return new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        int pre = 0;
        int beh = nums.length - 1;
        List<List<Integer>> res = new LinkedList<>();
        while(pre < beh){
            if(nums[pre] + nums[beh] > target) beh--;
            else if(nums[pre] + nums[beh] < target) pre++;
            else res.add(List.of(nums[pre++], nums[beh--]));
        }
        return res;
    }
}
